package algorithm.leetcode.I1to100;

import algorithm.leetcode.TreeNode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * 这题用提示的dp是不可行的,dp(k-1)推到dp(k)时,新加入的节点new TreeNode(k)既可以是根节点也可以是任意非根节点
 * 这样的话是无法满足dp问题的无后效性的
 * 正确解法:回溯
 */

public class Q95 {

    public List<TreeNode> generateTrees(int n) {
        return generateHelper(1, n);
    }


    /**
     * 递归地生成节点范围从begin到end的BST
     * @param begin
     * @param end
     * @return
     */
    public List<TreeNode> generateHelper(int begin, int end) {
        // List<TreeNode> res = new LinkedList<TreeNode>() {{add(null);}};
        List<TreeNode> res = new LinkedList<>();
        if (begin <= end) {
            // 从begin到end,每个数字都可以成为根节点
            for (int i = begin; i <= end; i++) {
                // 递归的生成范围从begin到i-1的可行左子树
                List<TreeNode> lefts = generateHelper(begin, i-1);
                // 递归的生成范围从i+1到end的可行右子树
                List<TreeNode> rights = generateHelper(i+1, end);
                for (TreeNode left : lefts) {
                    for (TreeNode right : rights) {
                        // 笛卡尔积地组合根节点和左右子树
                        TreeNode node = new TreeNode(i);
                        node.left = left;
                        node.right = right;
                        res.add(node);
                    }
                }
            }
        }
        // 如果begin > end,可行的树只有null节点,只有这种情况下才能添加,注意不能无脑添加
        else {
            res.add(null);
        }
        return res;
    }

    public static void main(String[] args) {
        Q95 q95 = new Q95();
        q95.generateTrees(2);
    }


}
